# @Time    : 2025/1/2 14:07
# @Author  : Zhang Yihao
import random
import time


class Sort:
    def __init__(self, n):
        """
        n是排序的数的数量
        :param n:
        """
        self.len=n    #被排序的列表的长度
        self.arr=[0]*n
        self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.arr[i]=random.randint(0,99)

    def partition(self,left,right):
        pivot=self.arr[left]
        while left<right:
            while left<right and self.arr[right]>=pivot:
                right-=1
            while left<right and self.arr[left]<=pivot:
                left+=1
            self.arr[left],self.arr[right]=self.arr[right],self.arr[left]

        self.arr[left]=pivot
        return left
    def quick_sort(self,left,right):
        if left>=right:
            return
        pivot=self.partition(left,right)
        self.quick_sort(left,pivot-1)
        self.quick_sort(pivot+1,right)

    def adjust_max_heap(self,pos,arr_len):
        """
        把某个字数调整为大根堆
        :param pos:
        :param arr_len:
        :return:
        """
        arr=self.arr
        dad=pos
        son=2*dad+1
        while son<arr_len:
            if son+1<arr_len and arr[son]<arr[son+1]:
                son+=1
            if arr[son]>arr[dad]:
                arr[son],arr[dad]=arr[dad],arr[son]
                dad=son
                son=2*dad+1
            else:
                break

    def heap_sort(self):
        # 大根堆
        for parent in range(self.len//2-1,-1,-1):
            self.adjust_max_heap(parent,self.len)
        arr=self.arr
        arr[0],arr[self.len-1]=arr[self.len-1],arr[0]
        for arr_len in range(self.len-1,1,-1):
            self.adjust_max_heap(0,arr_len)
            arr[0],arr[arr_len-1]=arr[arr_len-1],arr[0]

if __name__ == '__main__':
    my_sort=Sort(1000000)
    # print(my_sort.arr)
    start=time.time()
    my_sort.quick_sort(0,9)
    # my_sort.heap_sort()
    end=time.time()
    print('总耗时:{}s'.format(end-start))
    # print(my_sort.arr)

